﻿using System;
using System.Collections.Generic;

namespace SieveOfEratosthenes
{
    class SieveOfEratosthenes
    {
        static void PrintResult(List<int> numbers)
        {
            foreach (int number in numbers)
            {
                Console.Write("{0} ", number);
            }
            Console.WriteLine();
        }

        static List<int> Eratosthenes(int arrayLenght)
        {
            bool[] primesLeftArray = new bool[arrayLenght];
            int mainIndex = 2;

            while (mainIndex < arrayLenght)
            {
                //if square of the prime number is higher than the limit all Primes are found
                if (mainIndex * mainIndex > arrayLenght)
                {
                    break;
                }

                for (int nextNumber = mainIndex * mainIndex; nextNumber < arrayLenght; nextNumber += mainIndex)
                {
                    primesLeftArray[nextNumber] = true;
                }
                //check if next number is selected as a normal one
                for (mainIndex++; mainIndex < arrayLenght; mainIndex++)
                {
                    if (!primesLeftArray[mainIndex])
                    {
                        break;
                    }
                }
            }

            List<int> result = new List<int>();
            for (int index = 2; index < arrayLenght; index++)
            {
                if (!primesLeftArray[index])
                {
                    result.Add(index);
                }
            }
            return result;
        }

        static void Main()
        {
            int number = 10000000;

            List<int> numbers = Eratosthenes(number);

            PrintResult(numbers);
        }
    }
}
